package main.leetcode.clockin.July;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 329. 矩阵中的最长递增路径
 *
 * <p>给定一个整数矩阵，找出最长递增路径的长度。
 *
 * <p>对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
 *
 * <p>示例 1: 输入: nums = [ [9,9,4], [6,6,8], [2,1,1] ] 输出: 4 解释: 最长递增路径为 [1, 2, 6, 9]。
 *
 * <p>示例 2: 输入: nums = [ [3,4,5], [3,2,6], [2,2,1] ] 输出: 4 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
 */
public class day26 {
    //    private int res;
    //    private int m;
    //    private int n;

    public static void main(String[] args) {
        System.out.println(
                new day26().longestIncreasingPath(new int[][] {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}));
        System.out.println(
                new day26().longestIncreasingPath(new int[][] {{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}));
    }

    /** dfs，tle */
    //    public int longestIncreasingPath(int[][] matrix) {
    //        if (matrix == null || matrix.length == 0) {
    //            return 0;
    //        }
    //        m = matrix.length;
    //        n = matrix[0].length;
    //        for (int i = 0; i < m; ++i) {
    //            for (int j = 0; j < n; ++j) {
    //                dfs(matrix, i, j, Integer.MIN_VALUE, 0);
    //            }
    //        }
    //        return res;
    //    }
    //
    //    private void dfs(int[][] matrix, int i, int j, int last, int cur) {
    //        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || matrix[i][j] <= last) {
    //            res = Math.max(res, cur);
    //            return;
    //        }
    //        dfs(matrix, i - 1, j, matrix[i][j], cur + 1);
    //        dfs(matrix, i + 1, j, matrix[i][j], cur + 1);
    //        dfs(matrix, i, j - 1, matrix[i][j], cur + 1);
    //        dfs(matrix, i, j + 1, matrix[i][j], cur + 1);
    //    }

    //    /** dfs + 记忆集 */
    //    public int longestIncreasingPath(int[][] matrix) {
    //        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    //            return 0;
    //        }
    //        m = matrix.length;
    //        n = matrix[0].length;
    //        int[][] memo = new int[m][n];
    //        int res = 0;
    //        for (int[] ints : memo) {
    //            Arrays.fill(ints, -1);
    //        }
    //        for (int i = 0; i < m; ++i) {
    //            for (int j = 0; j < n; ++j) {
    //                res = Math.max(res, dfs(matrix, i, j, memo, Integer.MIN_VALUE));
    //            }
    //        }
    //        return res;
    //    }
    //
    //    private int dfs(int[][] matrix, int i, int j, int[][] memo, int last) {
    //        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || matrix[i][j] <= last) {
    //            return 0;
    //        }
    //        if (memo[i][j] != -1) {
    //            return memo[i][j];
    //        }
    //        int up = dfs(matrix, i - 1, j, memo, matrix[i][j]);
    //        int down = dfs(matrix, i + 1, j, memo, matrix[i][j]);
    //        int left = dfs(matrix, i, j - 1, memo, matrix[i][j]);
    //        int right = dfs(matrix, i, j + 1, memo, matrix[i][j]);
    //        return memo[i][j] = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    //    }

    /** 拓扑排序 */
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        // 基本参数
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 记录出度，出度方向代表该方向上的元素值比当前元素值要大
        int[][] outDegrees = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int[] dir : dirs) {
                    int newRow = i + dir[0], newCol = j + dir[1];
                    if (newRow >= 0
                            && newRow < m
                            && newCol >= 0
                            && newCol < n
                            // 注意这里是 >
                            && matrix[newRow][newCol] > matrix[i][j]) {
                        ++outDegrees[i][j];
                    }
                }
            }
        }

        // 记录bfs起点，即为当前区域内的最大值，也就是终点
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (outDegrees[i][j] == 0) {
                    queue.offer(new int[] {i, j});
                }
            }
        }

        // 广搜 + 拓扑排序
        int res = 0;
        while (!queue.isEmpty()) {
            ++res;
            int size = queue.size();
            for (int k = 0; k < size; ++k) {
                int[] curPos = queue.poll();
                int i = curPos[0], j = curPos[1];
                for (int[] dir : dirs) {
                    int newRow = i + dir[0], newCol = j + dir[1];
                    if (newRow >= 0
                            && newRow < m
                            && newCol >= 0
                            && newCol < n
                            // 注意这里是 <
                            && matrix[newRow][newCol] < matrix[i][j]) {
                        if (--outDegrees[newRow][newCol] == 0) {
                            queue.offer(new int[] {newRow, newCol});
                        }
                    }
                }
            }
        }
        return res;
    }
}
